package com.gitee.feizns.explore.data_structure.tree.bs.easy;

/**
 * @author feizns
 * @since 2019/12/24
 */
public class IsBalanced {

    private static TreeNode create() {
        TreeNode ret = new TreeNode(1);
        ret.left = new TreeNode(2);
        ret.left.left = new TreeNode(3);
        ret.left.left.left = new TreeNode(4);
        ret.right = new TreeNode(2);
        ret.right.right = new TreeNode(3);
        ret.right.right.right = new TreeNode(4);
        return ret;
    }

    public static void main(String[] args) {
        System.out.println(isBalanced(create()));
    }

    public static boolean isBalanced(TreeNode root) {
        return height(root) != -1;
    }

    private static int height(TreeNode root) {
        if ( root != null ) {
            int lh = height(root.left);
            if ( lh == -1 ) return -1;
            int rh = height(root.right);
            if ( rh == -1 ) return -1;
            return Math.abs(lh - rh) < 2 ? (Math.max(lh, rh)) + 1 : -1;
        }
        return 0;
    }

//    public static boolean isBalanced(TreeNode root) {
//        return isB(root).balanced;
//    }
//
//    private static HAndB isB(TreeNode root) {
//        if ( root != null ) {
//            HAndB lhb = isB(root.left);
//            HAndB rhb = isB(root.right);
//            if ( lhb.balanced && rhb.balanced ) {
//                if ( Math.abs(lhb.height - rhb.height) > 1 )
//                    return new HAndB(false);
//                return new HAndB(true, Math.max(lhb.height, rhb.height) + 1);
//            } else
//                return new HAndB(false);
//        }
//        return new HAndB(true);
//    }
//
//    private static int h(TreeNode n) {
//        return n == null ? 0 : Math.max(h(n.left), h(n.right)) + 1;
//    }
//
//    private static class HAndB {
//        boolean balanced;
//        int height;
//        public HAndB(boolean balanced) {
//            this.balanced = balanced;
//        }
//        public HAndB(boolean balanced, int height) {
//            this.balanced = balanced;
//            this.height = height;
//        }
//    }

}
